#include <algorithm>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <list>
#include <bitset>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <ctime>
#include <numeric>
#include <functional>
#include <valarray>
#include <complex>
#include <utility>
using namespace std;

const int dx[]={0,-1,0,1,-1,1, 1,-1};
const int dy[]={1,0,-1,0, 1,1,-1,-1};
const double eps=1e-8;

typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vgraph;
typedef vector<pii> vpii;
typedef vector<LL> vLL;
typedef vector<string> vs;

#define sz(a) (int)a.size()
#define fori(i,a,b) for(int i(a),_b(b);i<=_b;++i)
#define ford(i,a,b) for(int i(a),_b(b);i>=_b;--i)
#define forn(i,n) fori(i,0,n-1)
#define fora(i,a) forn(i,sz(a))
#define fore(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define clear0(a) memset(a,0,sizeof(a))
#define clearm1(a) memset(a,-1,sizeof(a))
#define maximum(a) (*max_element(all(a)))
#define minimum(a) (*min_element(all(a)))
#define findx(a,x) (find(all(a),x)-a.begin())
#define two(X) (1LL<<(X))
#define contain(S,X) ((S)&two(X))
#define setbit(S,X) ((S)|=two(X))
#define clearbit(S,X) ((S)&=~two(X))
#define togglebit(S,X) ((S)^=two(X))
#define sqr(a) ((a)*(a))
#define finp "input.inp"
#define fout "output.out"
#define nmax 50
#define mmax 100
#define kmax 20
#define modulo 1000000007
#define maxc 999999999

#define debugprint(a) cout << a << ' '
template <typename T>
void debugprintarr(T arr,int x, int y)
{
    fori(i,x,y) debugprint(arr[i]);
    cout << '\n';
}

template <typename T>
void debugprint2darr(T arr, int x1, int y1, int x2, int y2)
{
    fori(i,x1,y1) debugprintarr(arr[i],x2,y2);
}
struct hkr
{
    int x,y,w;
    bool operator< (const hkr &i) const
    {
        return w>i.w;
    }
};

priority_queue<hkr> hq;
int d[nmax][nmax],per[kmax],n,m,k,kq;
bool fr[nmax][nmax];
vpii restaurant;

void permutation(int cnt)
{
    if (cnt==k)
    {
        int db1=0,db2=0,max1=0,max2=0;
        forn(i,k)
        if (per[i])
        {
            db1+=2*d[restaurant[i].fi][restaurant[i].se];
            max1=max(max1,d[restaurant[i].fi][restaurant[i].se]);
        } else
        {
            db2+=2*d[restaurant[i].fi][restaurant[i].se];
            max2=max(max2,d[restaurant[i].fi][restaurant[i].se]);
        }
        db1-=max1; db2-=max2;
        kq=min(kq,max(db1,db2));
        return;
    }
    per[cnt]=0;
    permutation(cnt+1);
    per[cnt]=1;
    permutation(cnt+1);
    per[cnt]=0;
}
int cost(hkr i,hkr j,vs c)
{
    if (c[i.x][i.y]=='$' || c[j.x][j.y]=='$' || c[i.x][i.y]=='X' || c[j.x][j.y]=='X')
        return 2;
    int tmp=abs(c[i.x][i.y]-c[j.x][j.y]);
    if (tmp==0) return 1;
    if (tmp==1) return 3;
    return maxc;
}
bool inside(hkr v)
{
    return v.x>=0 && v.y >=0 && v.x<n && v.y<m;
}
void dijkstra(int sx,int sy,vs c)
{
    forn(i,n)
    forn(j,m)
    {
        d[i][j]=maxc;
        fr[i][j]=true;
    }
    d[sx][sy]=0;
    hkr u;
    u.x=sx; u.y=sy; u.w=0;
    hq.push(u);
    for(;!hq.empty();)
    {
        for(;;)
        {
            u=hq.top();
            hq.pop();
            if (hq.empty() || fr[u.x][u.y]) break;
        }
        if (!fr[u.x][u.y]) return;
        fr[u.x][u.y]=false;
        forn(i,4)
        {
            hkr v;
            v.x=u.x+dx[i];
            v.y=u.y+dy[i];
            if (inside(v))
            {
                int e=cost(u,v,c);
                if (fr[v.x][v.y] && d[v.x][v.y]>u.w+e)
                {
                    v.w=d[v.x][v.y]=u.w+e;
                    hq.push(v);
                }
            }
        }
    }
}
class PizzaDelivery {
public:
	int deliverAll(vector <string> terrain) {
		int u=0,v=0;
		restaurant.clear();
		n=sz(terrain);
		m=sz(terrain[0]);
		forn(i,n)
        forn(j,m)
        {
            if (terrain[i][j]=='X')
            {
                u=i;
                v=j;
            }
            if (terrain[i][j]=='$')
                restaurant.pb(mp(i,j));
        }
        k=sz(restaurant); kq=maxc;
        dijkstra(u,v,terrain);
        //debugprint2darr(d,0,n-1,0,m-1);
        forn(i,k)
        if (d[restaurant[i].fi][restaurant[i].se]==maxc) return -1;
        permutation(0);
        return kq;
	}
};


// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit-pf 2.3.0
#include <iostream>
#include <string>
#include <vector>
#include <ctime>
#include <cmath>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <string> p0, bool hasAnswer, int p1) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << "\"" << p0[i] << "\"";
	}
	cout << "}";
	cout << "]" << endl;
	PizzaDelivery *obj;
	int answer;
	obj = new PizzaDelivery();
	clock_t startTime = clock();
	answer = obj->deliverAll(p0);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p1 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p1;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	bool disabled;
	bool tests_disabled;
	all_right = true;
	tests_disabled = false;
	
	vector <string> p0;
	int p1;
	
	{
	// ----- test 0 -----
	disabled = false;
	string t0[] = {"3442211","34$221X","3442211"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 8;
	all_right = (disabled || KawigiEdit_RunTest(0, p0, true, p1) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	disabled = false;
	string t0[] = {"001000$","$010X0$","0010000"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 13;
	all_right = (disabled || KawigiEdit_RunTest(1, p0, true, p1) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	disabled = false;
	string t0[] = {"001000$","$010X0$","0010000","2232222","2222222","111$111"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = -1;
	all_right = (disabled || KawigiEdit_RunTest(2, p0, true, p1) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	disabled = false;
	string t0[] = {"001000$","$010X0$","0010000","1232222","2222222","111$111"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 28;
	all_right = (disabled || KawigiEdit_RunTest(3, p0, true, p1) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	disabled = false;
	string t0[] = {"X$$","$$$"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 14;
	all_right = (disabled || KawigiEdit_RunTest(4, p0, true, p1) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	disabled = false;
	string t0[] = {"0$245","$0221","11$11","$$000","111$$","10100","10101","$0001","1$021","21000","2$4$5","334$5","33433","44442","33344","223$2","23333","3$3$3","2222$","00$01","21$22","X4222","66677","7888$"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	all_right = (disabled || KawigiEdit_RunTest(5, p0, false, p1) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	}
	
	if (all_right) {
		if (tests_disabled) {
			cout << "You're a stud (but some test cases were disabled)!" << endl;
		} else {
			cout << "You're a stud (at least on given cases)!" << endl;
		}
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// END KAWIGIEDIT TESTING
